package 区间;

import org.junit.Test;

import java.util.*;

/**
 * 区间：
 *      头小->大 （相同时：尾大->小
 *
 * 本题还考 排序API
 *
 * 易错点：
 *      for < list.size()-1
 */
public class 删除被覆盖区间1288 {
    public int removeCoveredIntervals(int[][] intervals) {
        // 按 头 排序
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            list.add(new int[]{intervals[i][0], intervals[i][1]}); // 不用[2]
        }
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if(a[0] != b[0]){ // 头同
                    return a[0]-b[0]; // 小->大
                }else if(a[0] == b[0]){ // 头不同
                    return b[1]-a[1]; // 大->小
                }
                return 0; // 无用
            }
        });

        // 去除多余
        for (int i = 0; i < list.size()-1; i++) { // 里面比 i i+1, 所以外面到 n-2 即可
            // 可以不用 - 但不好理解了
//            if(list.get(i)[1] < list.get(i+1)[1]){
//                if(i==list.size()-2){
//                    return list.size(); // [[],[]]的情况
//                }
//                continue;
//            }
            while(list.get(i)[1] >= list.get(i+1)[1]){
                list.remove(i+1);
                if(i == list.size()-1){
                    return list.size(); // 没到for，while就给干到头了
                }
            }

            // 不用 while 只用for 的写法 -> 但是 庄总 遍历几个node 是一样的数量 （虽然 n2 复杂度）
            // 力扣试下速度 : 5ms->9ms , 快了一点点.. ?
//            for (int i = 1; i < intvs.length; i++) {
//                int[] intv = intvs[i];
//                // 情况一，找到覆盖区间
//                if (left <= intv[0] && right >= intv[1]) {
//                    res++;
//                }else{
//                    left = intv[0];
//                    right = intv[1];
//                }
//            }
        }
        return list.size();
    }

    /*
     LBLD
        思路：
            一共3种情况：覆盖 / 相交 / 相离

        速度比较：
            不用 while 只用for 的写法 -> 但是 庄总 遍历几个node 是一样的数量 （虽然 n2 复杂度）
            力扣试下速度 : 5ms->9ms , 快了一点点.. ?
    */
    int removeCoveredIntervals_LBLD(int[][] intvs) {
        // 按照起点升序排列，起点相同时降序排列
        Arrays.sort(intvs, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });

        // 记录合并区间的起点和终点
        int left = intvs[0][0];
        int right = intvs[0][1];

        int res = 0;
        for (int i = 1; i < intvs.length; i++) {
            int[] intv = intvs[i];
            // 情况一，找到覆盖区间
            if (left <= intv[0] && right >= intv[1]) {
                res++;
            }else{
                left = intv[0];
                right = intv[1];
            }
        }
        return intvs.length - res;
    }

    @Test
    public void test() {
        int[][] intervals = {{1,5}, {2,8}, {2,7}, {2,6}, {3,5}};
//        int[][] intervals = {{3,10}, {4,10}, {5,11}};
//        int[][] intervals = {{1,2}, {1,4}, {3,4}}; // 最后一个样例 31/32
        System.out.println(removeCoveredIntervals(intervals));
    }
}
